CF559C Gerald and Giant Chess

如果没有不能走到的点,这道题就非常简单了。我们只需向下走h1h-1步,向右走w1w-1步,就可到达右下角。在这h+w2h+w-2步中,我们选h1h-1向下走,那么答案为Ch+w2h1C_{h+w-2}^{h-1}

但是,棋盘中有些点是不能走的,我们考虑用容斥原理去除多余方案,即

Ans=Ch+w2h1P1+P2+..+(1)nPnAns=C_{h+w-2}^{h-1}-P_1+P_2+..+(-1)^n * P_n

其中,PiP_i经过ii个不能走的点的路径,但是,此题n<=2000n<=2000,容斥原理直接炸掉。

但上面的思路给了我们启示,设fif_i表示从(1,1)(1,1)走到第ii个不能走的点,且不经过其它不能走的点的方案数。那么有:

1.PNG

我们可以看出,转移时与下标先后顺序有关,我们先对下标排序,再进行计算。

我们将终点也看成一个不能走到的点,答案就为fn+1f_{n+1}

附上代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define Mod 1000000007

const int MAXN = 2000 , MAXDEX = 100000;
int h , w , n , f[ MAXN + 5 ];
int Fac[ 2 * MAXDEX + 5 ] , Inv[ 2 * MAXDEX + 5 ];
struct node{
    int x , y;
    bool operator < ( const node &Other ) {
        if( x < Other.x )
            return 1;
        if( x == Other.x && y < Other.y )
            return 1;
        return 0;
    }
}a[ MAXN + 5 ];

int Quick_pow( int x , int po ) {
    int Ans = 1;
    while( po ) {
        if( po % 2 )
            Ans = 1ll * Ans * x % Mod;
        x = 1ll * x * x % Mod;
        po /= 2;
    }
    return Ans;
}
void Init( ) {
    int M = 2 * max( h , w );
    Fac[ 0 ] = 1;
    for( int i = 1 ; i <= M ; i ++ )
        Fac[ i ] = 1ll * Fac[ i - 1 ] * i % Mod;
    Inv[ M ] = Quick_pow( Fac[ M ] , Mod - 2 );		//费马小定理算出阶乘最后一项逆元
    for( int i = M - 1 ; i >= 0 ; i -- )
        Inv[ i ] = 1ll * Inv[ i + 1 ] * ( i + 1 ) % Mod;
    
    /*for( int i = 1 ; i <= M ; i ++ )
        printf("%d %d\n",Fac[ i ],Inv[ i ]);*/
}

int Combination( int n , int m ) {	//根据组合数定义
    if( n < m ) return 0;
    return 1ll * Fac[ n ] * Inv[ n - m ] % Mod * Inv[ m ] % Mod;
}

int main( ) {
    scanf("%d %d %d",& h , &w , &n );
    for( int i = 1 ; i <= n ; i ++ )
        scanf("%d %d",&a[ i ].x,&a[ i ].y);
    n ++;
    a[ n ].x = h , a[ n ].y = w;
    sort( a + 1 , a + n + 1 );
    Init( );
    
    for( int i = 1 ; i <= n ; i ++ ) {
        f[ i ] = Combination( a[ i ].x + a[ i ].y - 2 , a[ i ].x - 1 );
        for( int j = 1 ; j <= i - 1 ; j ++ )
            f[ i ] = ( ( 1ll * f[ i ] - 1ll * f[ j ] * Combination( a[ i ].x + a[ i ].y - a[ j ].x - a[ j ].y , a[ i ].x - a[ j ].x ) % Mod ) % Mod + Mod ) % Mod;
    }
    printf("%d\n",f[ n ]);
    return 0;
}